In this section, we give formal proofs of perversity and
non-monotonicity in Erd\"{o}s-R\'{e}nyi random graphs. We have
observed the non-monotonicity is pervasive in wide range of contact
graphs, including scale-free graphs, Erd\"{o}s-R\'{e}nyi graphs, and
other synthetic or real world graphs. Theorem~\ref{thm:risk.gnp} gives
the rigorous proof of one-sided model and two-sided model for
Erd\"{o}s-R\'{e}nyi random graphs.

\begin{lemma}
\label{lem:2end-exist}
Given a complete graph as the contact network, for intervention with
any success probability $\ps$, there exists parameter set
$\pt,\pb,\pv$, such that there is non-monotonicity in two-sided risk
behavior model.
\end{lemma}
\begin{proof}
When nobody takes interventions, there are $n$ nodes in the graph,
and the disease transmission probability between each pair of nodes
is $\pt=\cc/n$, where $\cc > 1$. By~\cite{erdos1960}, there is a giant
connected component with high probability (size of the connected
component is $\Theta(n)$).

When everybody takes interventions, $\ps n+o(n)$ nodes will have
successful interventions with high probability, and thus removed from
the graph. The remaining $(1-\ps)n+o(n)$ nodes will all exhibit risk
behavior changes. Thus, the disease transmission probability between
each pair of nodes is $\pb=\cp / (1-\ps)n$, where $\cp >
1$. By~\cite{erdos1960}, there is a giant connected component with
high probability (size of the connected component is $\Theta(n)$).

Now we are going to show there exists a $\pv$, such that, if we apply
interventions to each node independently with probability $\pv$, the
epidemic severity will be $o(n)$ with high probability. Let $A$ be the
set of nodes that haven't taken interventions, $B$ be the set of nodes
that have taken interventions but failed, and $C$ be the set of nodes
that have taken interventions and succeeded. $r_A = 1-\pv$ represents
the probability of a random node being in set $A$, $r_B =
\pv\rb{1-\ps}$ represents the probability of a random node being in
set $B$, and $r_C = \pv\ps$ represents the probability of a random
node being in set $C$. In the two-sided model, disease transmits
with probability $\pb$ between nodes in set $C$, and $\pt$
otherwise. Set $a = \cc$ and $b = \cp / \rb{1-\ps}$. Let
\[M = \left( \begin{array}{ccc}
a r_A & a r_B & 0 \\
a r_A & b r_B & 0 \\
0 & 0 & 0
\end{array}\right)\]
This yields a model of inhomogeneous random graphs with 3 types of
vertices ($A$, $B$, and $C$).  By~\cite{soderberg+inhomo02} Theorem 1,
if all the eigenvalues of $M$ are less than 1 in absolute value, then
the size of the largest connected component is $o\rb{n}$. Let
$\lambda$ be the eigenvalues of $M$.
\begin{eqnarray*}
\det\rb{M-\lambda I} &=& \det\left[\begin{array}{ccc}
a r_A - \lambda & a r_B & 0\\
a r_A & b r_B - \lambda & 0 \\
0 & 0 & -\lambda
\end{array}\right] \\
 &=& -\lambda\rb{\rb{a r_A-\lambda}\rb{b r_B-\lambda} - a^2r_Ar_B} \\
 &=& -\lambda\rb{\lambda^2 - \rb{a r_A+b r_B}\lambda + ab r_Ar_B - a^2r_Ar_B}
\end{eqnarray*}
Solving $\det\rb{M-\lambda} = 0$, we have
\[\lambda_1 = \frac{\rb{a r_A+b r_B} + \sqrt{\Delta}}{2}, \lambda_2 = \frac{\rb{a r_A+b r_B} - \sqrt{\Delta}}{2}, \lambda_3 = 0\]
where $\Delta=\rb{a r_A-b r_B}^2 + 4a^2r_Ar_B$. Since $\abs{\lambda_3}
\le \abs{\lambda_2} \le \abs{\lambda_1}$, it is sufficient to show
there exists a set of parameters that yields $\abs{\lambda_1}<1$. Set
$\cp = \cc$.
\begin{eqnarray*}
\abs{\lambda_1} &=& \frac{\rb{a r_A+b r_B} + \sqrt{\rb{a r_A-b r_B}^2 + 4a^2r_Ar_B}}{2} \\
 &=& \frac{\cc\rb{1-\pv}+\cp\pv + \sqrt{\rb{\cc\rb{1-\pv}-\cp\pv}^2 + 4\cc^2\pv\rb{1-\pv}\rb{1-\ps}}}{2} \\
 &=& \cc\frac{\rb{1-\pv}+\pv+\sqrt{\rb{\rb{1-\pv}-\pv}^2+4\pv\rb{1-\pv}\rb{1-\ps}}}{2} \\
 &=& \cc\frac{1 + \sqrt{\rb{\rb{1-\pv}+\pv}^2 - 4\ps\pv\rb{1-\pv}}}{2} \\
 &=& \cc\frac{1 + \sqrt{1 - 4\ps\pv\rb{1-\pv}}}{2}
\end{eqnarray*}
When $0<\pv<1$, $\frac{1 + \sqrt{1 - 4\ps\pv\rb{1-\pv}}}{2}$ is a
constant smaller than 1. We can find $\cc>1$ that satisfies $c\frac{1
  + \sqrt{1 - 4\ps\pv\rb{1-\pv}}}{2} < 1$. Thus, for intervention with
success probability $\ps$, there exist parameters $\pv$, $\pt$, and
$\pb$, such that the epidemic size is $o\rb{n}$. This completes our
proof of this lemma.
\end{proof}

\begin{lemma}
\label{lem:1end-exist}
Given a complete graph as the contact network, for intervention with
any success probability $\ps$, there exists parameter set
$\pt,\pb,\pv$, such that there is non-monotonicity in one-sided risk
behavior model.
\end{lemma}
\begin{proof}
When nobody takes interventions, there are $n$ nodes in the graph,
and the disease transmission probability between each pair of nodes
is $\pt=\cc/n$, where $\cc < 1$. By~\cite{erdos1960}, the size of the
largest connected component is $O\rb{\log n}$ with high probability.

When everybody takes interventions, $\ps n+o\rb{n}$ nodes will have
successful interventions with high probability, and thus removed from
the graph. The remaining $\rb{1-\ps}n+o\rb{n}$ nodes will exhibit risk
behavior changes. Thus, the disease transmission probability between
each pair of nodes is $\pb=\cp/\rb{1-\ps}n$, where $\cp <
1$. By~\cite{erdos1960}, the size of the largest connected component
is $O\rb{\log n}$ with high probability.

Now we are going to show there exists a $\pv$, such that, if we apply
interventions to each node independently with probability $\pv$, the
epidemic severity will be $\Theta\rb{n}$ with high probability. Let
$A$ be the set of nodes that haven't taken interventions, $B$ be the
set of nodes that have taken interventions but failed, and $C$ be the
set of nodes that have taken interventions and succeeded. $r_A =
1-\pv$ represents the probability of a random node being in set $A$,
$r_B = \pv\rb{1-\ps}$ represents the probability of a random node
being in set $B$, and $r_C = \pv\ps$ represents the probability of a
random node being in set $C$. In the one-sided model, disease
transmit with probability $\pt$ between nodes in set $A$, and $\pb$
otherwise. Set $a = \cc$ and $b = \cp / \rb{1-\ps}$. Let
\[M = \left( \begin{array}{ccc}
a r_A & b r_B & 0 \\
b r_A & b r_B & 0 \\
0 & 0 & 0 \\
\end{array}\right)\]
This yields a model of inhomogeneous random graphs with 3 types of
vertices ($A$, $B$, and $C$).  By~\cite{soderberg+inhomo02} Theorem 1,
if some eigenvalue of $M$ is larger than 1, then the size of the
largest connected component is $\Theta\rb{n}$. Let $\lambda$ be the
eigenvalues of $M$.
\begin{eqnarray*}
\det\rb{M-\lambda I} &=& \det\left[\begin{array}{ccc}
a r_A - \lambda & b r_B & 0 \\
b r_A & b r_B - \lambda & 0 \\
0 & 0 & -\lambda \\
\end{array}\right] \\
 &=& -\lambda\rb{\rb{a r_A - \lambda}\rb{b r_B - \lambda} - b^2r_Ar_B} \\
 &=& -\lambda\rb{\lambda^2 - \rb{a r_A+b r_B}\lambda + ab r_Ar_B - b^2r_Ar_B} \\
\end{eqnarray*}
Solving $\det\rb{M-\lambda} = 0$, we have
\[\lambda_1 = \frac{\rb{a r_A+b r_B} + \sqrt{\Delta}}{2}, \lambda_2 = \frac{\rb{a r_A+b r_B} - \sqrt{\Delta}}{2}, \lambda_3 = 0\]
where $\Delta = \rb{a r_A-b r_B}^2+4b^2r_Ar_B$. Since
$\abs{\lambda_1} \ge \abs{\lambda_2} \ge \abs{\lambda_3}$, it is
sufficient to show there exists a set of parameters that yields
$\abs{\lambda_1}>1$. Let $\cc = \cp$.
\begin{eqnarray*}
\abs{\lambda_1} &=& \frac{\rb{a r_A+b r_B}+\sqrt{\rb{a r_A-b r_B}^2+4b^2r_Ar_B}}{2} \\
 &=& \frac{\cc\rb{1-\pv}+\cp\pv + \sqrt{\rb{\cc\rb{1-\pv}-\cp\pv}^2 + 4\cp^2\frac{\pv\rb{1-\pv}}{1-\ps}}}{2} \\
 &=& \cc\frac{\rb{1-\pv}+\pv+\sqrt{\rb{\rb{1-\pv}-\pv}^2 + 4\frac{\pv\rb{1-\pv}}{1-\ps}}}{2} \\
 &=& \cc\frac{1+\sqrt{\rb{\rb{1-\pv}-\pv}^2+4\pv\rb{1-\pv}-4\pv\rb{1-\pv}+4\frac{\pv\rb{1-\pv}}{1-\ps}}}{2} \\
 &=& \cc\frac{1+\sqrt{\rb{\rb{1-\pv}+\pv}^2 + 4\pv\rb{1-\pv}\rb{\frac{1}{1-\ps}-1}}}{2} \\
 &=& \cc\frac{1+\sqrt{1+4\pv\rb{1-\pv}\frac{\ps}{1-\ps}}}{2}
\end{eqnarray*}
When $0<\pv<1$,
$\frac{1+\sqrt{1+4\pv\rb{1-\pv}\frac{\ps}{1-\ps}}}{2}$ is
a constant greater than 1. We can find $\cc<1$ that satisfies
$\cc\frac{1+\sqrt{1+4\pv\rb{1-\pv}\frac{\ps}{1-\ps}}}{2} >
1$. Thus, for vaccination with success probability $\ps$, there
exist parameters $\pv$, $\pt$, and $\pb$, such that the epidemic
size is $\Theta\rb{n}$. This completes our proof of this lemma.
\end{proof}

\junk{
\begin{theorem}
\label{thm:gnp}
For the Erd\"{o}s-R\'{e}nyi random graph model $G(n,p^*)$, there exist
$\pt$, $\pb$, and $\ps$, such that (i) in the one-sided model, it
almost surely holds that the epidemic severity is $o(n)$ for both $\pv
= 0$ and $\pv = 1$, yet $\Theta(n)$ for some $\pv$ in $\rb{0,1}$; (ii)
in the two-sided model, the epidemic severity is $\Theta(n)$ for both
$\pv = 0$ and $\pv = 1$, yet $o(n)$ for some $\pv$ in $\rb{0,1}$.
\end{theorem}
}
Now we can show the proof of Theorem \ref{thm:risk.gnp} as follows.
\begin{proof}[Proof of Theorem \ref{thm:risk.gnp}]
We claim the disease transmission process on Erd\"{o}s-R\'{e}nyi
random graph $G(n,p^*)$ with parameter set $(\pt,\pb,\ps,\pv)$ is the
same as the disease transmission process on a complete graph with
parameter set $(p^* \pt, p^* \pb, \ps, \pv)$. It's simply because the
edge between each pair of nodes ``opens'' with the same probability in
both random processes. Thus, for any disease transmission process on
Erd\"{o}s-R\'{e}nyi random graph, we can reduce it to the
corresponding process on a complete graph. Then by Lemma
\ref{lem:2end-exist} and \ref{lem:1end-exist} we can conclude the
statement of this theorem holds.
\end{proof}

